/**
 * 1381. 设计一个支持增量操作的栈
 * https://leetcode-cn.com/problems/design-a-stack-with-increment-operation/
 */
public class Solutions_1381 {
    public static void main(String[] args) {
        CustomStack obj = new CustomStack(3);
        obj.push(1);
        obj.push(2);
        int res1 = obj.pop();  // output: 2
        System.out.println(res1);
        obj.push(2);
        obj.push(3);
        obj.push(4);
        obj.increment(5, 100);
        obj.increment(2, 100);
        int res2 = obj.pop();  // output: 103
        System.out.println(res2);
        int res3 = obj.pop();  // output: 202
        System.out.println(res3);
        int res4 = obj.pop();  // output: 201
        System.out.println(res4);
        int res5 = obj.pop();  // output: -1
        System.out.println(res5);
    }
}

class CustomStack {
    int[] arr = null;
    int[] adds = null;
    int top = -1;

    public CustomStack(int maxSize) {
        arr = new int[maxSize];
        adds = new int[maxSize];
    }

    public void push(int x) {
        if (top < arr.length - 1) {
            // 栈中还有容量时
            ++top;
            arr[top] = x;
        }
    }

    public int pop() {
        if (top == -1) {
            return -1;
        }
        // 弹出元素时，计算是否在增量的区间内，若在，那么 adds[top] 有值
        int ret = arr[top] + adds[top];
        if (top != 0) {
            // 关键
            adds[top - 1] += adds[top];
        }
        // 置 0
        adds[top] = 0;
        // 弹出元素后，指针左移
        -- top;
        return ret;
    }

    /**
     * 栈底的 k 个元素的值都增加 val
     * @param k
     * @param val
     */
    public void increment(int k, int val) {
        // 如果栈中元素总数小于 k，则栈中的所有元素都增加 val
        int limit = Math.min(k - 1, top);
        if (limit >= 0) {
            // 进行增量操作的截止索引处，加上增量
            adds[limit] += val;
        }
    }
}
